#include <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆，使其满足大根堆性质
void heapify(int arr[], int n, int i)
{
    int largest = i;       // 初始化最大元素为根结点
    int left = 2 * i + 1;  // 左子结点索引
    int right = 2 * i + 2; // 右子结点索引

    // 如果左子结点存在且大于根结点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子结点存在且大于当前最大结点
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是根结点
    if (largest != i)
    {
        printf("  Swap %d (root) and %d (largest)\n", arr[i], arr[largest]); // 交换根结点和最大子结点

        swap(&arr[i], &arr[largest]);

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(int arr[], int n)
{
    printf("Building max heap:\n"); // 构建大根堆

    // 构建大根堆（从最后一个非叶子结点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        printf("Heapify at index %d (value %d):\n", i, arr[i]); // 调整结点
        heapify(arr, n, i);

        // 打印当前堆状态
        printf("  Current heap: ");
        for (int j = 0; j < n; j++)
        {
            printf("%d ", arr[j]);
        }
        printf("\n");
    }

    printf("\nMax heap built: "); // 大根堆构建完成
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    printf("Sorting process:\n"); // 排序过程

    // 逐个提取元素
    for (int i = n - 1; i > 0; i--)
    {
        // 将当前根结点（最大值）移动到数组末尾
        printf("Move root (%d) to end, swap with %d\n", arr[0], arr[i]); // 将根结点移动到末尾

        swap(&arr[0], &arr[i]);

        // 对减小后的堆进行调整
        printf("Heapify root (new root: %d) on reduced heap (size %d)\n", arr[0], i); // 调整减小后的堆
        heapify(arr, i, 0);

        // 打印当前数组状态
        printf("  After step %d: ", n - i);
        for (int j = 0; j < n; j++)
        {
            printf("%d ", arr[j]);
        }
        printf("\n\n");
    }
}

int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: "); // 原始数组
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n\n");

    heapSort(arr, n); // 调用堆排序函数

    printf("\nSorted array: "); // 排序后的数组
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}